#include <iostream>
#include <stack>

using namespace std;

/*
Find the maximum rectangle (in terms of area) under a histogram in linear time. 
The area is of largest rectangle that fits entirely in the Histogram. 

Complexity: 4 steps:
1) Finding Li = O(n)
2) Finding Ri = O(n)
3) Calculating Ai = O(n)
4) Finding max A(i) = O(n)

So Final complexity is O(n) + O(n) + O(n) + O(n) = O(n)
*/

int LargestArea(int arr[], int len)  
{  
	int *area = NULL;   
	int i, leftIndex, rightIndex;  
	stack<int> St;
    
	area = (int*)malloc(sizeof(int)*len);
	if( !area ) return -1;

	// calculate the left side
	for(i=0; i<len; i++)  
	{  
		while (!St.empty())  
		{  
			if(arr[i] <= arr[St.top()])  
				St.pop();  
			else
				break; 
		} 

		if(St.empty())  
			leftIndex = -1;  
		else  
			leftIndex = St.top();  
		
		//Calculating Li  
		area[i] = i - leftIndex - 1;  
		St.push(i);  
	}  
      
	//clearing stack for finding Ri  
	while (!St.empty())  
		St.pop();  
      
	for (i=len-1; i>=0; i--)  
	{  
		while (!St.empty())  
		{  
			if(arr[i] <= arr[St.top()])  
				St.pop();  
			else  
				break;  
		}
		  
		if(St.empty())  
			rightIndex = len;  
		else  
			rightIndex = St.top();

		//calculating Ri, after this step area[i] = Li + Ri  
		area[i] += rightIndex - i -1;  
		St.push(i);  
	}
      
	//Calculating Area[i] and find max Area  
	int max = 0, finalIndex = 0;  
	for (i=0; i<len; i++)  
	{  
		area[i] = arr[i] * (area[i] + 1);  
		if (area[i] > max)  
		{
			max = area[i];  
			finalIndex = i;
		}
	}  
    free( area );
	cout<<"The final index is "<<finalIndex<<" with max value "<<max<<endl;
	return max;  
}  

int main()
{
	int Array[] = {9,6,2,1,3,5,4,8,2,7};
	int n = sizeof(Array)/sizeof(Array[0]);
	LargestArea(Array, n);
	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}
